//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 
//
// 说明：本题中，我们将空字符串定义为有效的回文串。 
//
// 示例 1: 
//
// 输入: "A man, a plan, a canal: Panama"
//输出: true
// 
//
// 示例 2: 
//
// 输入: "race a car"
//输出: false
// 
// Related Topics 双指针 字符串 
// 👍 268 👎 0

package leetcode.editor.cn;

//Java：验证回文串
public class P125ValidPalindrome {

    /**
     *
     * 思路： 双指针，判断非数字和非字母指针 左移/右移，然后如果字符不相等就算是false
     *
     * 执行用时： 4 ms , 在所有 Java 提交中击败了 67.06% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 50.60% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isPalindrome(String s) {
            int start = 0;
            int end = s.length() - 1;
            s = s.toUpperCase();
            while (start < end) {
                if (!check(s.charAt(start))) {
                    start++;
                    continue;
                }
                if (!check(s.charAt(end))) {
                    end--;
                    continue;
                }
                if (s.charAt(start) == s.charAt(end)) {
                    start++;
                    end--;
                } else {
                    return false;
                }
            }
            return true;
        }

        /**
         * 检查字符是不是字母或数字
         */
        private boolean check(char ch) {
            if (ch >= 'A' && ch <= 'Z') {
                return true;
            }
            if (ch >= '0' && ch <= '9') {
                return true;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P125ValidPalindrome().new Solution();
        System.out.println(solution.isPalindrome("A man, a plan, a canal: Panama"));
        // TO TEST
    }

}